class Solution {
    public void reorderList(ListNode head) {
        if (head == null) return;

        // Step 1: Find the middle of the list
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse the second half of the list
        ListNode pphead = new ListNode();
        ListNode cur = slow.next;
        slow.next = null; // Split the list into two halves
        while (cur != null) {
            ListNode next = cur.next;
            cur.next = pphead.next;
            pphead.next = cur;
            cur = next;
        }

        // Step 3: Merge the two halves
        ListNode cur1 = head;
        ListNode cur2 = pphead.next;
        while (cur1 != null && cur2 != null) {
            ListNode next1 = cur1.next;
            ListNode next2 = cur2.next;

            cur1.next = cur2;
            cur2.next = next1;

            cur1 = next1;
            cur2 = next2;
        }
    }
}